package org.gzc.sort;

import java.util.Arrays;

/**
 * @Description: 基数排序
 * @Author: guozongchao
 * @Date: 2020/8/8 23:56
 */
public class RadixSort implements SortStrategy{
    @Override
    public void sort(int[] array) {
        //找出序列的最大值
        int max = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        //获取该最大值的位数(作为排序的趟数)
        int maxLength = (max + "").length();

        //定义一个二维数组，表示 10 个桶, 每个桶就是一个一维数组
        // 说明
        // 1. 二维数组包含 10 个一维数组
        // 2. 为了防止在放入数的时候，数据溢出，则每个一维数组(桶)，大小定为 array.length
        // 3. 基数排序是使用空间换时间的经典算法
        int[][] bucket = new int[10][array.length];
        //定义一个一位数组，记录每个桶的元素个数
        int[] bucketElementCounts = new int[10];

        //从低位到高位开始，个位、百位、千位......
        //依次遍历序列元素，在每一趟中，将元素加入到对应的桶
        for (int i = 0,n=1; i < maxLength; i++,n*=10) {
            for (int j = 0; j < array.length; j++) {
                int digitOfElement = array[j] / n % 10;  //获得元素的个位 或者 十位 或者 百位.....的数字
                //将该元素加入到对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = array[j];
                bucketElementCounts[digitOfElement]++;
            }

            //设置原数组的初始索引
            int index=0;
            //再将桶中的数据依次取出放回原来数组
            for (int k = 0; k < 10; k++) {
                //如果桶中的元素个数不为0，就将该桶的元素依次取出，放回原数组
                if (bucketElementCounts[k] != 0) {
                    for (int m = 0; m < bucketElementCounts[k]; m++) {
                        array[index++] = bucket[k][m];
                    }
                }
                //取完后，必须将该桶的元素个数清0
                bucketElementCounts[k]=0;
            }

          //  System.out.println("第"+(i+1)+"趟排序结果为："+ Arrays.toString(array));
        }
    }
}
